//当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
//
// 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
//
//
//
// 示例 1:
//
//
//输入: n = 10
//输出: 9
//
//
// 示例 2:
//
//
//输入: n = 1234
//输出: 1234
//
//
// 示例 3:
//
//
//输入: n = 332
//输出: 299
//
//
//
//
// 提示:
//
//
// 0 <= n <= 10⁹
//
//
// Related Topics 贪心 数学 👍 377 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function monotoneIncreasingDigits(n: number): number {

    let strArr: number[] = String(n).split('').map(i => parseInt(i));
    const length = strArr.length;
    //? 用一个flag来标记从哪里开始赋值9
    let flag: number = length;
    //? 从后往前遍历
    for (let i = length - 2; i >= 0; i--) {
        //? 不满足单调增
        if (strArr[i] > strArr[i + 1]) {
            //? 这位 - 1， 后面的需要赋9 这里不怕0因为要赋9
            strArr[i] -= 1;
            flag = i + 1;
        }
    }
    for (let i = flag; i < length; i++) {
        strArr[i] = 9;
    }
    return parseInt(strArr.join(''));

};
//leetcode submit region end(Prohibit modification and deletion)
